import string
from numpy import random, array
import observer

# some aux functions
def findInversed(num, prime):
    '''
    exhaustive search of inversed element in GF(prime)
    '''
    for i in range(1, prime):
        if (i*num)%prime == 1:
            return i
def interPoly(x, i, xVector, prime):
    """
    calculate value of i'th laGrange polynomial
    """
    numerator = 1
    denominator = 1
    for j, xj in enumerate(xVector):
        if j != i:
            numerator *= (x - xj)%prime
            numerator = numerator%prime
            denominator *= (xVector[i] - xj)%prime
            denominator = denominator%prime
    return (numerator * findInversed(denominator, prime))%prime

class KeyCollector:
    def __init__(self, prime):
        #self.key = key
        self.prime = prime
        # parse file "ranks.txt" to get number of different type of observers
        ranksFile = open("ranks.txt", "r")
        ranksLines = [ line.rstrip() for line in ranksFile.readlines() ]
        lines = []
        for line in ranksLines:
            if len(line) == 0 or line[0] == '#':
                continue
            lines.append(line)
        self.ranks = {}
        for line in lines:
            linesplit = line.split(": ")
            self.ranks[linesplit[0]] = int(linesplit[1])
        
        # dict of collected keys
        self.keysCollected = {}.fromkeys(self.ranks.keys())
        for rank in self.keysCollected:
            self.keysCollected[rank] = []

    def getKey(self, observer):
        '''
        observer is Observer class instance
        '''
        observerRank = observer.rank
        observerKey = observer.key
        
        # check if observer's key has already been collected
        if observerKey in self.keysCollected[observerRank]:
            print "This key has already been collected"
            return
        else:
            self.keysCollected[observerRank].append(observerKey)
            return

    def restoreSecret(self):
        # check if there are enough keys to restore secret
        for rank in self.ranks.keys():
            if len(self.keysCollected[rank]) < self.ranks[rank]:
                print "Not enough keys to restore secret"
                return
        print "Enough keys to restore secret"
        secret = 1
        for rank in self.ranks.keys():
            xVector = array([k[0] for k in self.keysCollected[rank]])
            yVector = array([k[1] for k in self.keysCollected[rank]])
            lValues = array([interPoly(0, i, xVector, self.prime) for i, xi in enumerate(xVector)])
            secret *= sum(lValues*yVector)%self.prime
        return secret%self.prime
